1. Field of the Invention
Aspects of the present invention relate to techniques for bar code assisted positioning. More particularly, aspects of the present invention relate to techniques for bar code assisted positioning using Two-Dimensional (2D) bar codes.
2. Description of the Related Art
A Global Navigation Satellite System (GNSS) provides autonomous geo-spatial positioning with global coverage. The GNSS allows electronic receivers to determine their location (i.e., longitude, latitude, and altitude) to within a few meters using time signals transmitted along a line-of-sight by radio from satellites. Receivers on the ground with a fixed position may also be used to calculate the precise time as a reference for scientific experiments. As of 2009, the United States NAVSTAR Global Positioning System (GPS) is the only fully operational GNSS. The Russian GLONASS is a GNSS in the process of being restored to full operation. China has indicated it will expand its regional Beidou navigation system into the global COMPASS navigation system by 2015. The European Union's Galileo positioning system is a GNSS in initial deployment phase, scheduled to be operational in 2013.
Mobile Stations (MSs) with embedded Global Positioning System (GPS) capabilities are becoming a reality. The development of these MSs is being fuelled, in part, by the U.S. Federal Communications Commission's Emergency (E)-911 mandate requiring the position of an MS to be available to emergency call dispatchers. GPS enabled MSs will not only address E-911 but will also enable wireless Location Based Services (LBSs), which are emerging as a new opportunity for mobile network operators to generate new revenues. Services such as driving directions, identifying closest banks or restaurants, and tracking of people for social networking, safety or in emergency situations (via E-911 in North America and E-112 in Europe) are currently being deployed by wireless network operators.
LBSs rely on some method of computing a user's location. One simple method uses the nearest cell tower as an approximate position; this method is referred to as Cell IDentifier (ID) and is currently used by operators that have already introduced commercial LBS. While Cell ID accuracy (i.e., the size of the cell tower coverage, normally several kilometers) is adequate for a number of applications, it is clearly not sufficient to meet the demands of applications such as E-911. Thus, advanced positioning methods that leverage mobile-network resources have been proposed. These techniques can be divided into network-based and handset-based solutions such as GPS and in particular, Assisted-GPS (A-GPS). A GPS Satellite Constellation is described below with reference to FIG. 1.
FIG. 1 illustrates a GPS Satellite Constellation according to the related art.
Referring to FIG. 1, the GPS system, which is run by the US Department of Defense through an Air Force space division, uses a constellation of twenty-four satellites 1-24 around the earth 104. The satellites 1-24 are positioned in six Earth-centered orbital planes with four satellites in each plane. For example, satellites 17-20 are included in orbital plane 106.
A GPS receiver should be able to receive signals from about 10 satellites at a time in ideal circumstances, but far fewer can be received up reliably in most real-world conditions. All of the satellites constantly transmit data (e.g., the navigation message) over the same set of frequencies, using an encoding that allows 50 bits per second for a total of 1,500 bits of data to be demodulated from each satellite every 30 seconds.
On every minute and half-minute, each satellite transmits its notion of the precise time and its health, followed by its location and a path in orbit (i.e., the ephemeris) that is valid for as long as four hours. Each satellite also transmits a subset of data about the other satellites in orbit (i.e., the almanac), including a rougher position. It takes 25 navigation messages, all received perfectly over 12.5 minutes from a single satellite, to assemble a full almanac. A timestamp is also included as part of each 300-bit (six-second) segment or sub-frame of the message.
GPS satellites circle the earth twice a day in a very precise orbit and transmit signal information to earth. GPS receivers take this information and use triangulation to calculate a user's exact location. Essentially, the GPS receiver compares the time a signal was transmitted by a satellite with the time it was received. The time difference is used by the GPS receiver to determine how far away the satellite is. Now, with distance measurements from a few more satellites, the receiver can determine the user's position. A GPS receiver must be locked onto the signal of at least three satellites to calculate a Two-Dimensional (2D) position (i.e., latitude and longitude) as described below with reference to FIG. 2.
FIG. 2 illustrates 2D positioning based on three satellites according to the related art.
Referring to FIG. 2, a possible location 202 is determined using geometric trilateration based signals received from three satellites. With four or more satellites in view, the receiver can determine the user's Three-Dimensional (3D) position (i.e., latitude, longitude, and altitude) as described below with reference to FIG. 3.
FIG. 3 illustrates 3D positioning based on four satellites according to the related art.
Referring to FIG. 3, a possible location 302 is determined using geometric trilateration based on signals received from four satellites.
The satellites have highly accurate atomic clocks but the GPS receiver generally has a much less accurate and less expensive clock. As a result, the GPS receiver will not correctly determined the amount of time that it took for the radio waves to travel from the satellites. Accordingly, an incorrect position may be determined. Thus, an additional satellite signal is needed to correct the time error in order to determine the correct position.
GPS satellites transmit two low power radio signals, designated L1 and L2. Civilian GPS uses the L1 frequency of 1575.42 MegaHertz (MHz) in the Ultra High Frequency (UHF) band. The signals travel by line of sight, meaning they will pass through clouds, glass and plastic but will not pass through most solid objects, such as buildings and mountains.
A GPS signal contains three different bits of information, namely a pseudorandom code, ephemeris data, and almanac data. The pseudorandom code is simply an ID code that identifies which satellite is transmitting information. Ephemeris data is a set of parameters that can be used to accurately calculate the location of a GPS satellite at a particular point in time. The ephemeris data describes the path that the satellite is following as the satellite orbits the Earth. The GPS almanac is a set of data that every GPS satellite transmits, and the GPS almanac includes information about the state (health) of the entire GPS satellite constellation, and coarse data on every satellite's orbit. When a GPS receiver has current almanac data in memory, the GPS receiver can acquire satellite signals and determine initial position more quickly.
The receiver measures the transmit time of each message and computes the distance to each satellite. Geometric trilateration as shown in FIG. 2 and FIG. 3 is used to combine these distances with the location of the satellites to determine the receiver's location. In certain conditions, a conventional standalone GPS device has difficulty providing reliable positions in poor signal conditions. For example, when surrounded by tall buildings (resulting in multipath), or when the satellite signals are weakened when the GPS device is used indoors or under trees. In addition, when first turned on in these conditions, some GPS devices may not be able to download the almanac and ephemeris information from the GPS satellites, rendering them unable to function until a clear signal can be received continuously for up to 40 seconds.
It takes a minimum of 18 seconds after acquiring the signal to decode the ephemeris from the broadcast message, assuming that it did not drop or lose any data bits. In practice, Time-To-First-Fix (TTFF), when decoding ephemeris data, is in the range of 20-60 seconds for environments where the receiver has an unobstructed view of the sky. If the environment is harsh, such as an urban canyon or even indoors, the receiver may take much longer to recover the data bits, if it can recover them at all.
An A-GPS receiver can address these problems in several ways, using network elements such as either an assistance server or other data from a network. That assistance generally falls into two categories; information used to more quickly acquire satellites, or calculations done remotely. Some possible forms for GPS assistance data includes the following:                A list of visible satellites        Predicted GPS satellite Doppler and Doppler rates        Azimuth and elevation angles for the visible satellites        GPS satellite ephemeris information        GPS almanac        Satellite clock correction terms        Approximate GPS time        Precise GPS time        
A drawback of A-GPS is that the receiver requires access to an external network for accessing the assistance server. Moreover, some devices such as cameras can include an internal GPS receiver or connect to an external GPS device to obtain and add location information to the photos. However, these devices may not have access to an external network to obtain the assistance data. Furthermore, a device may not be able to reach an assistance server via a wireless link due to poor coverage or other reasons.
Accordingly, current positioning systems based on GPS suffer from large delays in determining an exact location because the GPS receiver needs to receive GPS data such as ephemeris and almanac information from the satellites before a location can be determined. While an A-GPS receiver may address these problems by using network elements such as an assistance server that can provide GPS assistance data to the receiver, the GPS receiver has a drawback in that it requires access to an external network for accessing the assistance server.
Another emerging trend in mobile services is bar codes, which are fast gaining traction as enablers for online content and services. Bar codes storing addresses and Uniform Resource Locators URLs may appear in magazines, on signs, buses, business cards or just about any object that users might need information about. Users with an MS including a camera function that are equipped with the correct reader software can scan the image of the bar code causing the MS's browser to launch and redirect to the programmed URL. This act of linking from physical world objects is known as a hardlink or physical world hyperlinks. Users can also generate and print their own bar codes for others to scan.
Both One-Dimensional (1D) and 2D bar codes exist. 1D bar codes (also referred to as linear bar codes) are one of the most widespread and well-known global identification applications and can be found anywhere in the world. The standards for 1D bar codes have been developed and adopted since the early 1970's. 1D bar codes are read by laser-based scanners (currently at point-of-sale and throughout the supply chain) and camera-based readers. An example of a 1D bar code is described below with reference to FIG. 4.
FIG. 4 illustrates a Universal Product Code (UPC) bar code according to the related art.
Referring to FIG. 4, the UPC has encoded therein a Global Trade Identification Number (GTIN). Here, the first and last digits are always placed outside the symbol to indicate Quiet Zones that are necessary for bar code scanners to work properly.
2D bar codes may contain more information than 1D linear bar codes, such as the UPC code. 1D bar codes get wider as more data is encoded. In contrast, the 2D bar codes make use of the vertical dimension to pack in more data.
Several 2D bar code symbologies have been standardized by the International Organization for Standardization (ISO) and the International Electrotechnical Commission (IEC). The ISO/IEC 18004 standard specifies a 2D bar code symbology referred to as Quick Response (QR) code. An exemplary QR code will be described below with reference to FIG. 5.
FIG. 5 illustrates a structure of a Version 7 symbol of a QR 2005 code according to the related art.
Referring to FIG. 5, the QR 2005 code symbol is constructed of nominally square modules set out in a regular square array and each includes an encoding region and function patterns. The encoding region includes format information 502, version information 504, and data and error correction codewords 506. The function patterns include a finder pattern 512, a separator 514, timing patterns 516, and alignment patterns 518. Payload data is not encoded in the function patterns. The QR 2005 code symbol is surrounded on all four sides by a quiet zone 520.
QR 2005 codes come in a variety of sizes. For example, there are forty sizes of QR 2005 code symbols, which are referred to as Version 1, Version 2 . . . . Version 40. Version 1 measures 21 modules×21 modules, Version 2 measures 25 modules×25 modules and so on increasing in steps of 4 modules per side up to Version 40 which measures 177 modules×177 modules. The QR 2005 code illustrated in FIG. 5 is an example of a Version 7 of a QR code symbol. A Version 1 of a QR 2005 code symbol is described below with reference to FIG. 6.
FIG. 6 illustrates a structure of a Version 1 symbol of a QR 2005 code according to the related art.
Referring to FIG. 6, the Version 1 symbol of the QR 2005 code measures 21 modules×21 modules. The data is encoded in 2×4 blocks 600 with each block carrying 8-bits of data, namely bits 0-7.
2D codes may be encoded with a higher bit density by employing color, an example of which is described below with reference to FIG. 7.
FIG. 7 illustrates a High Capacity Color Bar code (HCCB) according to the related art.
Referring to FIG. 7, the HCCB code is a type of bar code that uses colored triangles, instead of black-and-white lines or squares used by other bar code systems. The HCCB code may also be referred to as a Microsoft™ Tag.